package com.goudan.practice.tree;

import java.util.Objects;

/**
 * 一棵树是否是另一棵树的子树
 */
public class SunTree {
    public static class Node<right> {
        public int val;
        public Node left;
        public Node right;

        public Node(int val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {

    }

    public static boolean checkSon(Node n1, Node n2) {
        if (n2 == null) return true;
        if (n1 == null) return false;
        boolean eq = eqTree(n1, n2);
        boolean left = checkSon(n1.left, n2);
        boolean right = checkSon(n1.right, n2);
        return left || right || eq;
    }

    public static boolean eqTree(Node n1, Node n2) {
        if (n1 == n2) return true;
        if (n1 == null || n2 == null) return false;
        boolean eq = Objects.equals(n1.val, n2.val);
        boolean left = eqTree(n1.left, n2.left);
        boolean right = eqTree(n1.right, n2.right);
        return eq && left && right;
    }
}
